import java.util.*;

//二刷：bfs
class Solution {
    boolean canTransfer(String str1, String str2) {
        int diffCount = 0;
        for (int i = 0; i < str1.length(); i++) {
            if (str1.charAt(i) != str2.charAt(i)) {
                diffCount++;
                if (diffCount > 1) {
                    return false;
                }
            }
        }
        return diffCount == 1;
    }

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if (wordList.indexOf(endWord) < 0) {
            return 0;
        }
        wordList.add(beginWord);
        int start = wordList.size() - 1;
        List<List<Integer>> grid = new ArrayList<>(wordList.size());
        for (int i = 0; i < wordList.size(); i++) {
            grid.add(new ArrayList());
        }
        for (int i = 0; i < wordList.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (canTransfer(wordList.get(i), wordList.get(j))) {
                    grid.get(i).add(j);
                    grid.get(j).add(i);
                }
            }
        }

        boolean[] visited = new boolean[wordList.size()];
        visited[start] = true;
        Queue<Integer> queue = new ArrayDeque<>();
        int end = wordList.indexOf(endWord);
        queue.offer(start);
        int level = 0;
        int levelCount = 1;
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            if (cur == end) {
                return level + 1;
            }
            for (int to : grid.get(cur)) {
                if (!visited[to]) {
                    queue.offer(to);
                    visited[to] = true;
                }
            }
            levelCount--;
            if (levelCount == 0) {
                level++;
                levelCount = queue.size();
            }
        }
        return 0;
    }
}


//二刷：最短路径
class Solution1 {
    boolean canTransfer(String str1, String str2) {
        int diffCount = 0;
        for (int i = 0; i < str1.length(); i++) {
            if (str1.charAt(i) != str2.charAt(i)) {
                diffCount++;
                if (diffCount > 1) {
                    return false;
                }
            }
        }
        return diffCount == 1;
    }

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if (wordList.indexOf(endWord) < 0) {
            return 0;
        }
        wordList.add(beginWord);
        List<List<Integer>> grid = new ArrayList<>(wordList.size());
        for (int i = 0; i < wordList.size(); i++) {
            grid.add(new ArrayList());
        }
        for (int i = 0; i < wordList.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (canTransfer(wordList.get(i), wordList.get(j))) {
                    grid.get(i).add(j);
                    grid.get(j).add(i);
                }
            }
        }
        for (int i = 0; i < grid.size(); i++) {
            System.out.println(grid.get(i));
        }

        int[] minDist = new int[wordList.size()];
        Arrays.fill(minDist, Integer.MAX_VALUE);
        minDist[wordList.size() - 1] = 0;
        boolean[] visited = new boolean[wordList.size()];
        for (int i = 1; i < wordList.size(); i++) {
            int curDist = Integer.MAX_VALUE;
            int cur = -1;
            for (int j = 0; j < wordList.size(); j++) {
                if (!visited[j] && minDist[j] < curDist) {
                    curDist = minDist[j];
                    cur = j;
                }
            }
            System.out.println(cur);
            if (cur == -1) {
                break;
            }
            visited[cur] = true;
            for (int to : grid.get(cur)) {
                if (!visited[to] && curDist + 1 < minDist[to]) {
                    minDist[to] = curDist + 1;
                }
            }
        }
        if (minDist[wordList.indexOf(endWord)] == Integer.MAX_VALUE) {
            return 0;
        }
        return minDist[wordList.indexOf(endWord)] + 1;
    }
}

//class Solution {
//    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
//        return bfs(beginWord, endWord, wordList);
//    }
//
//    private int bfs(String beginWord, String endWord, List<String> wordList) {
//        Map<String, Integer> dis = new HashMap<>();
//        Queue<String> queue = new ArrayDeque<>();
//        queue.add(beginWord);
//        dis.put(beginWord, 1);
//        while (!queue.isEmpty()) {
//            String cur = queue.poll();
//            int curDis = dis.get(cur);
//            for (String next : wordList) {
//                if (!dis.containsKey(next) && getDiff(cur, next) == 1) {
//                    if (next.equals(endWord)) {
//                        return curDis + 1;
//                    }
//                    queue.offer(next);
//                    dis.put(next, curDis + 1);
//                }
//            }
//        }
//        return 0;
//    }
//
//    private int getDiff(String word, String other) {
//        int diff = 0;
//        for (int i = 0; i < word.length(); i++) {
//            if (word.charAt(i) != other.charAt(i)) {
//                diff++;
//            }
//        }
//        return diff;
//    }
//}

public class Main {
    public static void main(String[] args) {
        System.out.println(new Solution().ladderLength("hit", "cog",
                Arrays.asList("hot", "dot", "dog","lot","log","cog")));
    }
}